#include<vector>
using namespace std;

class Solution {
private:
    void diagonalSort(vector<vector<int>>& mat, int start_i,int start_j,int end_i,int end_j) {
        if (start_i >= end_i) return;
        int mid_i = start_i + (end_i - start_i) / 2;
        int mid_j = start_j + (end_j - start_j) / 2;
        diagonalSort(mat, start_i, start_j, mid_i, mid_j);
        diagonalSort(mat, mid_i+1, mid_j+1, end_i, end_j);
        int rows = mat.size();
        int cols = mat[0].size();
        vector<int>tmp(end_i - start_i + 1);
        int index = 0;
        int index1 =0, index2 = 0;
        while (index < tmp.size()) {
            if (index2 > (end_i - mid_i - 1) || (index1 <= (mid_i - start_i) &&
                mat[start_i + index1][start_j + index1] < mat[mid_i + 1 + index2][mid_j + 1 + index2]
                )) {
                tmp[index++] = mat[start_i + index1][start_j + index1];
                ++index1;
            }
            else {
                tmp[index++] = mat[mid_i + 1 + index2][mid_j + 1 + index2];
                ++index2;
            }
        }
        for (int i = 0; i < tmp.size(); ++i) {
            mat[start_i + i][start_j + i] = tmp[i];
        }

    }
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        if (mat.size() < 2) return mat;
        int cols = mat[0].size();
        int rows = mat.size();
        for (int start = 0; start < rows || start < cols; ++start) {
            if (start < cols) {
                int end = cols - 1 - start;
                if (end < rows)
                    diagonalSort(mat, 0, start, end, cols - 1);
                else
                    diagonalSort(mat, 0, start, rows - 1, rows - 1 + start);
            }
            if (start != 0 && start < rows) {
                int end = start + cols - 1;
                if (end < rows)
                    diagonalSort(mat, start, 0, end, cols - 1);
                else
                    diagonalSort(mat, start, 0, rows - 1, rows - 1 - start);
            }
        }
        return mat;
    }
};